/*
** $Id: ltable.c,v 2.118.1.4 2018/06/08 16:22:51 roberto Exp $
** Lua tables (hash)
** See Copyright Notice in lua.h
*/

#define ltable_c
#define LUA_CORE

#include "lprefix.h"


/*
** Implementation of tables (aka arrays, objects, or hash tables).
** Tables keep its elements in two parts: an array part and a hash part.
** Non-negative integer keys are all candidates to be kept in the array
** part. The actual size of the array is the largest 'n' such that
** more than half the slots between 1 and n are in use.
** Hash uses a mix of chained scatter table with Brent's variation.
** A main invariant of these tables is that, if an element is not
** in its main position (i.e. the 'original' position that its hash gives
** to it), then the colliding element is in its own main position.
** Hence even when the load factor reaches 100%, performance remains good.
*/

#include <math.h>
#include <limits.h>

#include "lua.h"

#include "ldebug.h"
#include "ldo.h"
#include "lgc.h"
#include "lmem.h"
#include "lobject.h"
#include "lstate.h"
#include "lstring.h"
#include "ltable.h"
#include "lvm.h"


/*
** Maximum size of array part (MAXASIZE) is 2^MAXABITS. MAXABITS is
** the largest integer such that MAXASIZE fits in an unsigned int.
*/
#define MAXABITS  cast_int(sizeof(int) * CHAR_BIT - 1)
#define MAXASIZE  (1u << MAXABITS)

/*
** Maximum size of hash part is 2^MAXHBITS. MAXHBITS is the largest
** integer such that 2^MAXHBITS fits in a signed int. (Note that the
** maximum number of elements in a table, 2^MAXABITS + 2^MAXHBITS, still
** fits comfortably in an unsigned int.)
*/
#define MAXHBITS  (MAXABITS - 1)

/** 将以n除以t的长度取模为索引取Node */
#define hashpow2(t, n)    (gnode(t, lmod((n), sizenode(t))))

/** 获取字符串为key的Node */
#define hashstr(t, str)    hashpow2(t, (str)->hash)
/** 获取布尔值为key的Node */
#define hashboolean(t, p)  hashpow2(t, p)
/** 获取整数为key的Node */
#define hashint(t, i)    hashpow2(t, i)


/*
** for some types, it is better to avoid modulus by power of 2, as
** they tend to have many 2 factors.
*/
#define hashmod(t, n)  (gnode(t, ((n) % ((sizenode(t)-1)|1))))


#define hashpointer(t, p)  hashmod(t, point2uint(p))


#define dummynode    (&dummynode_)

static const Node dummynode_ = {
        {NILCONSTANT},  /* value */
        {{NILCONSTANT, 0}}  /* key */
};


/*
** Hash for floating-point numbers.
** The main computation should be just
**     n = frexp(n, &i); return (n * INT_MAX) + i
** but there are some numerical subtleties.
** In a two-complement representation, INT_MAX does not has an exact
** representation as a float, but INT_MIN does; because the absolute
** value of 'frexp' is smaller than 1 (unless 'n' is inf/NaN), the
** absolute value of the product 'frexp * -INT_MIN' is smaller or equal
** to INT_MAX. Next, the use of 'unsigned int' avoids overflows when
** adding 'i'; the use of '~u' (instead of '-u') avoids problems with
** INT_MIN.
*/
#if !defined(l_hashfloat)

static int l_hashfloat(lua_Number n) {
    int i;
    lua_Integer ni;
    n = l_mathop(frexp)(n, &i) * -cast_num(INT_MIN);
    if (!lua_numbertointeger(n, &ni)) {  /* is 'n' inf/-inf/NaN? */
        lua_assert(luai_numisnan(n) || l_mathop(fabs)(n) == cast_num(HUGE_VAL));
        return 0;
    } else {  /* normal case */
        unsigned int u = cast(unsigned int, i) + cast(unsigned int, ni);
        return cast_int(u <= cast(unsigned int, INT_MAX) ? u : ~u);
    }
}

#endif


/*
** returns the 'main' position of an element in a table (that is, the index
** of its hash value)
*/
static Node *mainposition(const Table *t, const TValue *key) {
    switch (ttype(key)) {
        case LUA_TNUMINT:
            return hashint(t, ivalue(key));
        case LUA_TNUMFLT:
            return hashmod(t, l_hashfloat(fltvalue(key)));
        case LUA_TSHRSTR:
            return hashstr(t, tsvalue(key));
        case LUA_TLNGSTR:
            return hashpow2(t, luaS_hashlongstr(tsvalue(key)));
        case LUA_TBOOLEAN:
            return hashboolean(t, bvalue(key));
        case LUA_TLIGHTUSERDATA:
            return hashpointer(t, pvalue(key));
        case LUA_TLCF:
            return hashpointer(t, fvalue(key));
        default:
            lua_assert(!ttisdeadkey(key));
            return hashpointer(t, gcvalue(key));
    }
}


/*
** returns the index for 'key' if 'key' is an appropriate key to live in
** the array part of the table, 0 otherwise.
*/
static unsigned int arrayindex(const TValue *key) {
    if (ttisinteger(key)) {
        lua_Integer k = ivalue(key);
        if (0 < k && (lua_Unsigned) k <= MAXASIZE)
            return cast(unsigned int, k);  /* 'key' is an appropriate array index */
    }
    return 0;  /* 'key' did not match some condition */
}

/*
** returns the index of a 'key' for table traversals. First goes all
** elements in the array part, then elements in the hash part. The
** beginning of a traversal is signaled by 0.
*/
/**
 * 在给定的表中查找指定键的索引。
 *
 * @param L Lua状态机指针。
 * @param t 要查找的表。
 * @param key 要查找的键（栈中的位置）。
 * @return 返回键在表中的索引。如果键为nil，返回0（表示第一次迭代）。
 *         如果键在数组部分，返回其在数组中的索引；
 *         如果键在哈希部分，返回其在哈希表中的索引（加上数组部分的大小）。
 *
 * @note 如果键无效（未找到），会抛出运行时错误。
 */
static unsigned int findindex(lua_State *L, Table *t, StkId key)
{
    unsigned int i;
    if (ttisnil(key))
        return 0; /* first iteration */
    i = arrayindex(key);
    if (i != 0 && i <= t->sizearray)  /* is 'key' inside array part? */
        return i;  /* yes; that's the index */
    else {
        int nx;
        Node *n = mainposition(t, key);
        for (;;) {  /* check whether 'key' is somewhere in the chain */
            /* key may be dead already, but it is ok to use it in 'next' */
            if (luaV_rawequalobj(gkey(n), key) ||
                (ttisdeadkey(gkey(n)) && iscollectable(key) &&
                 deadvalue(gkey(n)) == gcvalue(key))) {
                i = cast_int(n - gnode(t, 0));  /* key index in hash table */
                /* hash elements are numbered after array ones */
                return (i + 1) + t->sizearray;
            }
            nx = gnext(n);
            if (nx == 0)
                luaG_runerror(L, "invalid key to 'next'");  /* key not found */
            else n += nx;
        }
    }
}

/**
 * 这个函数的作用是找到表中的下一个非空元素，并将其键和值推到 Lua 栈上
 */
int luaH_next(lua_State *L, Table *t, StkId key) {
    unsigned int i = findindex(L, t, key);  /* find original element */
    for (; i < t->sizearray; i++) {  /* try first array part */
        if (!ttisnil(&t->array[i])) {  /* a non-nil value? */
            setivalue(key, i + 1);
            setobj2s(L, key + 1, &t->array[i]);
            return 1;
        }
    }
    for (i -= t->sizearray; cast_int(i) < sizenode(t); i++) {  /* hash part */
        if (!ttisnil(gval(gnode(t, i)))) {  /* a non-nil value? */
            setobj2s(L, key, gkey(gnode(t, i)));
            setobj2s(L, key + 1, gval(gnode(t, i)));
            return 1;
        }
    }
    return 0;  /* no more elements */
}


/*
** {=============================================================
** Rehash
** ==============================================================
*/

/*
** Compute the optimal size for the array part of table 't'. 'nums' is a
** "count array" where 'nums[i]' is the number of integers in the table
** between 2^(i - 1) + 1 and 2^i. 'pna' enters with the total number of
** integer keys in the table and leaves with the number of keys that
** will go to the array part; return the optimal size.
*/
static unsigned int computesizes(unsigned int nums[], unsigned int *pna) {
    int i;
    unsigned int twotoi;  /* 2^i (candidate for optimal size) */
    unsigned int a = 0;  /* number of elements smaller than 2^i */
    unsigned int na = 0;  /* number of elements to go to array part */
    unsigned int optimal = 0;  /* optimal size for array part */
    /* loop while keys can fill more than half of total size */
    for (i = 0, twotoi = 1;
         twotoi > 0 && *pna > twotoi / 2;
         i++, twotoi *= 2) {
        if (nums[i] > 0) {
            a += nums[i];
            if (a > twotoi / 2) {  /* more than half elements present? */
                optimal = twotoi;  /* optimal size (till now) */
                na = a;  /* all elements up to 'optimal' will go to array part */
            }
        }
    }
    lua_assert((optimal == 0 || optimal / 2 < na) && na <= optimal);
    *pna = na;
    return optimal;
}


static int countint(const TValue *key, unsigned int *nums) {
    unsigned int k = arrayindex(key);
    if (k != 0) {  /* is 'key' an appropriate array index? */
        nums[luaO_ceillog2(k)]++;  /* count as such */
        return 1;
    } else
        return 0;
}


/*
** Count keys in array part of table 't': Fill 'nums[i]' with
** number of keys that will go into corresponding slice and return
** total number of non-nil keys.
*/
static unsigned int numusearray(const Table *t, unsigned int *nums) {
    int lg;
    unsigned int ttlg;  /* 2^lg */
    unsigned int ause = 0;  /* summation of 'nums' */
    unsigned int i = 1;  /* count to traverse all array keys */
    /* traverse each slice */
    for (lg = 0, ttlg = 1; lg <= MAXABITS; lg++, ttlg *= 2) {
        unsigned int lc = 0;  /* counter */
        unsigned int lim = ttlg;
        if (lim > t->sizearray) {
            lim = t->sizearray;  /* adjust upper limit */
            if (i > lim)
                break;  /* no more elements to count */
        }
        /* count elements in range (2^(lg - 1), 2^lg] */
        for (; i <= lim; i++) {
            if (!ttisnil(&t->array[i - 1]))
                lc++;
        }
        nums[lg] += lc;
        ause += lc;
    }
    return ause;
}


static int numusehash(const Table *t, unsigned int *nums, unsigned int *pna) {
    int totaluse = 0;  /* total number of elements */
    int ause = 0;  /* elements added to 'nums' (can go to array part) */
    int i = sizenode(t);
    while (i--) {
        Node *n = &t->node[i];
        if (!ttisnil(gval(n))) {
            ause += countint(gkey(n), nums);
            totaluse++;
        }
    }
    *pna += ause;
    return totaluse;
}


static void setarrayvector(lua_State *L, Table *t, unsigned int size) {
    unsigned int i;
    luaM_reallocvector(L, t->array, t->sizearray, size, TValue);
    for (i = t->sizearray; i < size; i++)
        setnilvalue(&t->array[i]);
    t->sizearray = size;
}


static void setnodevector(lua_State *L, Table *t, unsigned int size) {
    if (size == 0) {  /* no elements to hash part? */
        // node指向 dummynode_
        t->node = cast(Node *, dummynode);  /* use common 'dummynode' */
        t->lsizenode = 0;
        // lastfree设置为空
        t->lastfree = NULL;  /* signal that it is using dummy node */
    } else {
        int i;
        int lsize = luaO_ceillog2(size);
        if (lsize > MAXHBITS)
            luaG_runerror(L, "table overflow");
        size = twoto(lsize);
        t->node = luaM_newvector(L, size, Node);
        for (i = 0; i < (int) size; i++) {
            Node *n = gnode(t, i);
            gnext(n) = 0;
            setnilvalue(wgkey(n));
            setnilvalue(gval(n));
        }
        t->lsizenode = cast_byte(lsize);
        // 将lastfree指向节点的最后一个元素
        t->lastfree = gnode(t, size);  /* all positions are free */
    }
}


typedef struct {
    Table *t;
    unsigned int nhsize;
} AuxsetnodeT;


static void auxsetnode(lua_State *L, void *ud) {
    AuxsetnodeT *asn = cast(AuxsetnodeT *, ud);
    setnodevector(L, asn->t, asn->nhsize);
}


// L：Lua状态机，用于内存管理和错误处理等
// t：指向需要调整大小的Table的指针
// nasize：新的数组部分大小
// nhsize：新的哈希部分大小
void luaH_resize(lua_State *L, Table *t, unsigned int nasize,
                 unsigned int nhsize) {
    unsigned int i;
    int j;
    AuxsetnodeT asn; // 用于辅助设置新哈希部分的结构体
    unsigned int oldasize = t->sizearray; // 保存旧的数组部分大小
    int oldhsize = allocsizenode(t); // 计算并保存旧的哈希表大小（Node数量）
    Node *nold = t->node;  /* 保存旧的哈希节点指针，以便后续数据迁移和释放 */

    // 如果新数组大小大于旧数组大小，先扩展数组部分
    if (nasize > oldasize)
        setarrayvector(L, t, nasize); // 分配更大的数组，新元素初始为nil

    /* 创建新的哈希部分 */
    asn.t = t;
    asn.nhsize = nhsize;
    // 以保护模式执行哈希部分调整，防止内存分配错误导致状态不一致
    if (luaD_rawrunprotected(L, auxsetnode, &asn) != LUA_OK) {  /* 内存错误？ */
        setarrayvector(L, t, oldasize);  // 恢复数组到原始大小
        luaD_throw(L, LUA_ERRMEM);  // 重新抛出内存错误异常
    }

    // 如果新数组大小小于旧数组大小，需要收缩数组部分
    if (nasize < oldasize) {
        t->sizearray = nasize; // 更新数组大小
        /* 重新插入即将消失的数组元素（从nasize到oldasize-1）到表中 */
        for (i = nasize; i < oldasize; i++) {
            // 只处理非nil值，将其作为整数键重新插入（可能进入哈希部分）
            if (!ttisnil(&t->array[i]))
                luaH_setint(L, t, i + 1, &t->array[i]); // Lua数组索引从1开始，故i+1
        }
        // 收缩数组内存分配
        luaM_reallocvector(L, t->array, oldasize, nasize, TValue);
    }

    /* 重新插入旧哈希部分中的所有元素到新表中 */
    for (j = oldhsize - 1; j >= 0; j--) {
        Node *old = nold + j; // 获取旧哈希表中的节点
        if (!ttisnil(gval(old))) { // 检查节点的值是否为非nil
            /* 不需要GC屏障或使缓存无效，因为该条目已存在于表中 */
            // 将键值对重新插入到调整后的表t中
            setobjt2t(L, luaH_set(L, t, gkey(old)), gval(old));
        }
    }

    // 如果旧的哈希表大小大于0（非虚拟节点），则释放旧哈希节点数组占用的内存
    if (oldhsize > 0)
        luaM_freearray(L, nold, cast(size_t, oldhsize)); /* 释放旧的哈希数组 */
}


void luaH_resizearray(lua_State *L, Table *t, unsigned int nasize) {
    int nsize = allocsizenode(t);
    luaH_resize(L, t, nasize, nsize);
}

/*
** nums[i] = number of keys 'k' where 2^(i - 1) < k <= 2^i
*/
static void rehash(lua_State *L, Table *t, const TValue *ek) {
    unsigned int asize;  /* optimal size for array part */
    unsigned int na;  /* number of keys in the array part */
    unsigned int nums[MAXABITS + 1];
    int i;
    int totaluse;
    for (i = 0; i <= MAXABITS; i++) nums[i] = 0;  /* reset counts */
    na = numusearray(t, nums);  /* count keys in array part */
    totaluse = na;  /* all those keys are integer keys */
    totaluse += numusehash(t, nums, &na);  /* count keys in hash part */
    /* count extra key */
    na += countint(ek, nums);
    totaluse++;
    /* compute new size for array part */
    asize = computesizes(nums, &na);
    /* resize the table to new computed sizes */
    luaH_resize(L, t, asize, totaluse - na);
}


/*
** }=============================================================
*/


Table *luaH_new(lua_State *L) {
    GCObject *o = luaC_newobj(L, LUA_TTABLE, sizeof(Table));
    Table *t = gco2t(o);
    t->metatable = NULL;
    t->flags = cast_byte(~0);
    t->array = NULL;
    t->sizearray = 0;
    // 新创建table，sizearray为0，size为0
    setnodevector(L, t, 0);
    return t;
}


void luaH_free(lua_State *L, Table *t) {
    if (!isdummy(t))
        luaM_freearray(L, t->node, cast(size_t, sizenode(t)));
    luaM_freearray(L, t->array, t->sizearray);
    luaM_free(L, t);
}


static Node *getfreepos(Table *t) {
    if (!isdummy(t)) {
        // 从后往前，找到第一个空闲的节点
        while (t->lastfree > t->node) {
            t->lastfree--;
            if (ttisnil(gkey(t->lastfree)))
                return t->lastfree;
        }
    }
    return NULL;  /* could not find a free place */
}


/*
** 向哈希表插入一个新键。
** 首先检查键的主位置是否空闲。如果不是，则检查冲突节点是否在其自身的主位置上：
**   如果冲突节点不在其主位置上，则将其移动到一个空闲位置，并将新键放入其主位置；
**   如果冲突节点就在其自身的主位置上，则将新键放入一个空闲位置。
** inserts a new key into a hash table; first, check whether key's main
** position is free. If not, check whether colliding node is in its main
** position or not: if it is not, move colliding node to an empty place and
** put new key in its main position; otherwise (colliding node is in its main
** position), new key goes to an empty position.
*/
/**
 * 关键机制解释：
    1. ​主位置 (Main Position)​​:
        每个键通过哈希函数计算后，在哈希表中都有一个理想的位置，称为主位置。mainposition(t, key)函数就用于计算这个位置。
    2. 哈希冲突解决​​:
        Lua 的哈希表采用​​开放寻址法​​的一个变体来处理冲突。当两个键的主位置相同时，会发生冲突。
        Lua 使用了一个巧妙的​​链表​​来连接所有主位置相同的键，但这个链表是通过在节点中存储 next字段（指向下一个冲突节点的​​偏移量​​）来实现的，
        所有节点仍然存储在连续的内存数组里。代码主要处理两种情况：
            • ​​情况一​​ (othern != mp)：当前占据新键主位置 mp的节点（称为"冲突节点"）并不在它自己的主位置上（它是因为之前的冲突被放到这里的）。
                这时，Lua 会​​将这个"冲突节点"移动​​到另一个空闲位置 f，并调整相应的链表指针。这样，新键就可以被放入它自己的主位置 mp。
            • ​​情况二​​ (othern == mp)：冲突节点就在它自己的主位置上。这时，新键会被​​放入一个空闲位置 f​​，并将这个新位置 f链接到以 mp为头部的冲突链表中。

    3. ​​扩容机制 (Rehash)​​:
        当函数调用 getfreepos(t)也找不到任何空闲位置时，意味着哈希表已满。这时会触发 rehash函数。
        • rehash会​​重新计算​​表格的数组部分和哈希部分的大小。
        • 它会统计表中所有的​​整数键​​，并根据规则决定将哪些整数键对应的值​​移动到扩容后的数组部分​​，以提升效率。
        • 接着，它会​​调整哈希表的大小​​（通常是扩容），并​​重新插入​​所有键值对到新的空间中。
        • 最后，rehash返回后，luaH_newkey会​​递归调用​​ luaH_set尝试将键插入到扩容后的新表中。

    4. ​​键的处理​​: 
        函数会检查 key 是否为 nil或 NaN，这两种情况在 Lua 中都是​​非法​​的 table 键，会抛出错误。
        对于​​浮点数​​键，函数会尝试将其转换为整数（例如 1.0变成 1）。如果转换成功，则使用整数作为键，这有助于某些整数键能被放在了更高效的数组部分。
        这个过程确保了 Lua table 在插入操作时的高效性，同时根据键的分布动态调整内部结构。
 **/
TValue *luaH_newkey(lua_State *L, Table *t, const TValue *key) {
    Node *mp;
    TValue aux;
    // 检查key是否为nil（Lua table的key不能为nil）
    if (ttisnil(key)) luaG_runerror(L, "table index is nil");
    // 检查key是否为浮点数（可能可以转换为整数）
    else if (ttisfloat(key)) {
        lua_Integer k;
        // 尝试将浮点数key转换为整数（例如 1.0 -> 1）
        if (luaV_tointeger(key, &k, 0)) {  /* does index fit in an integer? */
            setivalue(&aux, k);
            key = &aux;  /* 将其作为整数插入 */
        } else if (luai_numisnan(fltvalue(key))) // 检查是否为NaN（NaN也不能作为key）
            luaG_runerror(L, "table index is NaN");
    }
    // 计算key的主位置（在哈希表中的理想位置）
    mp = mainposition(t, key);
    // 如果主位置已被占用（非nil）或是虚拟节点（dummy node）
    if (!ttisnil(gval(mp)) || isdummy(t)) {  /* main position is taken? */
        Node *othern;
        Node *f = getfreepos(t);  /* 获取一个空闲位置 */
        // 如果找不到空闲位置，需要重新哈希（扩容）表格
        if (f == NULL) {  /* cannot find a free place? */
            rehash(L, t, key);  /* 增长表格 */
            /* 调用'newkey'的函数会处理元方法缓存 */
            return luaH_set(L, t, key);  /* 将key插入扩容后的表格 */
        }
        lua_assert(!isdummy(t));
        // 找到当前占据主位置节点(mp)的"原本"主位置
        othern = mainposition(t, gkey(mp)); // 这里通过gkey(mp)得到当前占据目标key主位置的key，然后计算这个占据位置的节点的主位置
        // 拿到占用key主位置的节点的主位置的节点（有点拗口，多念几次就搞明白了），然后遍历这个节点的相同hash链表，
        // 直到找到占用主位置的节点的前一个节点（目的是将当前占用主节点的节点，挪到空闲位置，然后把位置腾给key（因为key的主位置在这里，必须给它））
        // 情况1：当前占据主位置的节点并不在其"原本"的主位置上（说明它是之前冲突被移动过来的）
        if (othern != mp) {  /* is colliding node out of its main position? */
            /* 是的；将冲突节点移动到空闲位置f */
            // 进入while循环前，othern指向占用key主位置的节点的主位置（也就是说，占用key主位置的节点（此处指mp）的主位置）
            // 目的是从占用key主位置的节点（mp）的主位置节点开始，遍历，直到找到mp的前一个节点，然后这个节点链接到mp的新位置上
            while (othern + gnext(othern) != mp)  /* find previous */
                othern += gnext(othern);
            // 将mp的hash表上的前一个节点othern的next指针指向新的空闲位置f（调整链表关系，因为mp将要放到这个空闲位置上）
            // 计算偏移量（这里需要明白，两个指针类型计算，得到的是类型偏移值，而不是字节偏移值）
            gnext(othern) = cast_int(f - othern);  /* rechain to point to 'f' */
            // 将mp节点的内容（key, value, next）复制到空闲位置f
            *f = *mp;  /* copy colliding node into free pos. (mp->next also goes) */
            // 如果mp原本有链后续冲突节点（next不为0），需要修正f的next指针
            if (gnext(mp) != 0) {
                // 调整f的next指针（因为mp移动到了f，next偏移量需要重新计算）
                gnext(f) += cast_int(mp - f);  /* correct 'next' */
                gnext(mp) = 0;  /* 现在'mp'是空闲的了，需要将其next指针置为0，因为它暂时不在链表中（指的是此刻） */
            }
            // 将原mp位置的值设为nil（现在它空闲了,将它设置为空闲，这样key就可以用这个node了）
            setnilvalue(gval(mp));
        // 情况2：当前占据主位置的节点就在其"原本"的主位置上
        } else {  /* colliding node is in its own main position */
            // 如果key的主位置正好放着一个主位置相同的节点，说明位置相同hash节点占用了（hash冲突）
            // 这种情况下，就把新节点放到空闲位置f，然后将f链接到这个冲突链表上
            /* 新节点将被放入空闲位置f */
            // 如果mp已经有链后续冲突节点（next不为0）
            if (gnext(mp) != 0)
                // 设置f的next指针，连接到mp的后续链表上
                gnext(f) = cast_int((mp + gnext(mp)) - f);  /* chain new position */
            else
                // 否则确保f的next指针为0
                lua_assert(gnext(f) == 0);
            // 将mp的next指针指向新的空闲位置f（将f加入链表）
            gnext(mp) = cast_int(f - mp);
            // 将mp指向新的空闲位置f，后续操作将把新key放入这里
            mp = f;
        }
    }
    // 无论哪种情况，现在mp指向的位置都可以用于存放新的key
    setnodekey(L, &mp->i_key, key); // 将key设置到节点中
    // 这里设置下内存屏障，将table染成灰色的，并加入到grayagin列表中，防止被错误的回收（因为在传播的原子阶段，会扫描这个链表，将其染黑）
    luaC_barrierback(L, t, key);    // 内存屏障，用于垃圾收集器
    lua_assert(ttisnil(gval(mp)));  // 断言确保节点的value为nil（是新插入的）
    // 获取这个节点的i_value所在的地址，并返回
    return gval(mp);
}


/*
** search function for integers
*/
const TValue *luaH_getint(Table *t, lua_Integer key) {
    // 如果key>1, 并且key小于数组大小，说明位于数组部分，直接从数组中拿值
    /* (1 <= key && key <= t->sizearray) */
    if (l_castS2U(key) - 1 < t->sizearray)
        return &t->array[key - 1];
    else {
        // 开始遍历hashtable部分
        Node *n = hashint(t, key);
        for (;;) {  /* check whether 'key' is somewhere in the chain */
            // 此处判断一点更要判断key的值是否等于gkey(n)的值，因为有可能key和gkey(n)的类型不同，但是值相同
            if (ttisinteger(gkey(n)) && ivalue(gkey(n)) == key)
                return gval(n);  /* that's it */
            else {
                // 拿到相同hash值的下一个节点
                int nx = gnext(n); // nx其实就是一个offset，相对于当前节点的offset
                if (nx == 0) break;
                n += nx; // 指向hash冲突表中的下一个节点
            }
        }
        return luaO_nilobject;
    }
}


/*
** search function for short strings
*/
const TValue *luaH_getshortstr(Table *t, TString *key) {
    Node *n = hashstr(t, key);
    lua_assert(key->tt == LUA_TSHRSTR);
    for (;;) {  /* check whether 'key' is somewhere in the chain */
        const TValue *k = gkey(n);
        // 判断是不是字符串，如果是字符串，再判断字符串值是否相等
        if (ttisshrstring(k) && eqshrstr(tsvalue(k), key))
            return gval(n);  /* that's it */
        else {
            // 不是字符串，或者字符串不相等，继续找下一个（hashtable）
            int nx = gnext(n);
            if (nx == 0)
                return luaO_nilobject;  /* not found */
            n += nx;
        }
    }
}


/*
** "Generic" get version. (Not that generic: not valid for integers,
** which may be in array part, nor for floats with integral values.)
*/
static const TValue *getgeneric(Table *t, const TValue *key) {
    Node *n = mainposition(t, key);
    for (;;) {  /* check whether 'key' is somewhere in the chain */
        if (luaV_rawequalobj(gkey(n), key))
            return gval(n);  /* that's it */
        else {
            int nx = gnext(n);
            if (nx == 0)
                return luaO_nilobject;  /* not found */
            n += nx;
        }
    }
}


const TValue *luaH_getstr(Table *t, TString *key) {
    if (key->tt == LUA_TSHRSTR)
        return luaH_getshortstr(t, key);
    else {  /* for long strings, use generic case */
        TValue ko;
        setsvalue(cast(lua_State * , NULL), &ko, key);
        return getgeneric(t, &ko);
    }
}


/*
** main search function
* 根据key寻找table中的value
*/
const TValue *luaH_get(Table *t, const TValue *key) {
    switch (ttype(key)) {
        case LUA_TSHRSTR:
            return luaH_getshortstr(t, tsvalue(key));
        case LUA_TNUMINT:
            return luaH_getint(t, ivalue(key));
        case LUA_TNIL:
            return luaO_nilobject;
        case LUA_TNUMFLT: {
            lua_Integer k;
            if (luaV_tointeger(key, &k, 0)) /* index is int? */
                return luaH_getint(t, k);  /* use specialized version */
            /* else... */
        }  /* FALLTHROUGH */
        default:
            return getgeneric(t, key);
    }
}


/*
** beware: when using this function you probably need to check a GC
** barrier and invalidate the TM cache.
*/
TValue *luaH_set(lua_State *L, Table *t, const TValue *key) {
    const TValue *p = luaH_get(t, key);
    if (p != luaO_nilobject)
        return cast(TValue *, p);
    else return luaH_newkey(L, t, key);
}


void luaH_setint(lua_State *L, Table *t, lua_Integer key, TValue *value) {
    // 先找到key对应的value所在的地址
    const TValue *p = luaH_getint(t, key);
    // cell表示一个key对应在table中的内存地址
    TValue *cell;
    // 如果key存在，则直接将p强制转换成cell
    if (p != luaO_nilobject)
        cell = cast(TValue *, p);
    else {
        // key对应没有node节点，则新建一个key（对应分配放置value的节点-node，这个node会包含值的指针，这个指针就是cell，用于存放值）
        TValue k;
        setivalue(&k, key);
        cell = luaH_newkey(L, t, &k);
    }
    // 将value中的值赋值给cell
    setobj2t(L, cell, value);
}


static lua_Unsigned unbound_search(Table *t, lua_Unsigned j) {
    lua_Unsigned i = j;  /* i is zero or a present index */
    j++;
    /* find 'i' and 'j' such that i is present and j is not */
    while (!ttisnil(luaH_getint(t, j))) {
        i = j;
        if (j > l_castS2U(LUA_MAXINTEGER) / 2) {  /* overflow? */
            /* table was built with bad purposes: resort to linear search */
            i = 1;
            while (!ttisnil(luaH_getint(t, i))) i++;
            return i - 1;
        }
        j *= 2;
    }
    /* now do a binary search between them */
    while (j - i > 1) {
        lua_Unsigned m = (i + j) / 2;
        if (ttisnil(luaH_getint(t, m))) j = m;
        else i = m;
    }
    return i;
}


/*
** Try to find a boundary in table 't'. A 'boundary' is an integer index
** such that t[i] is non-nil and t[i+1] is nil (and 0 if t[1] is nil).
*/
lua_Unsigned luaH_getn(Table *t) {
    unsigned int j = t->sizearray;
    if (j > 0 && ttisnil(&t->array[j - 1])) {
        /* there is a boundary in the array part: (binary) search for it */
        unsigned int i = 0;
        while (j - i > 1) {
            unsigned int m = (i + j) / 2;
            if (ttisnil(&t->array[m - 1])) j = m;
            else i = m;
        }
        return i;
    }
        /* else must find a boundary in hash part */
    else if (isdummy(t))  /* hash part is empty? */
        return j;  /* that is easy... */
    else return unbound_search(t, j);
}


#if defined(LUA_DEBUG)

Node *luaH_mainposition (const Table *t, const TValue *key) {
  return mainposition(t, key);
}

int luaH_isdummy (const Table *t) { return isdummy(t); }

#endif
